def factorial(n):
    # 基线条件
    if n == 0 or n == 1:
        return 1
    # 递归条件
    return n * factorial(n - 1)

print(factorial(5))  # 120







factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * 1)))  # 基线条件触发
120









def fibonacci(n):
    # 基线条件
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # 递归条件
    return fibonacci(n-1) + fibonacci(n-2)

print([fibonacci(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]









from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n < 2:
        return n
    return fibonacci_memo(n-1) + fibonacci_memo(n-2)

print(fibonacci_memo(50))  # 12586269025 (普通递归无法快速计算)





def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n-1, n*accumulator)

print(factorial_tail(5))  # 120




import os

def scan_directory(path, indent=0):
    """递归扫描目录结构"""
    print(' ' * indent + os.path.basename(path) + '/')
    for item in os.listdir(path):
        item_path = os.path.join(path, item)
        if os.path.isdir(item_path):
            scan_directory(item_path, indent+4)
        else:
            print(' ' * (indent+4) + item)

# scan_directory('.')  # 扫描当前目录


def hanoi(n, source, target, auxiliary):
    if n > 0:
        # 将n-1个盘子从源柱移动到辅助柱
        hanoi(n - 1, source, auxiliary, target)

        # 移动第n个盘子到目标柱
        print(f"Move disk {n} from {source} to {target}")

        # 将n-1个盘子从辅助柱移动到目标柱
        hanoi(n - 1, auxiliary, target, source)


hanoi(3, 'A', 'C', 'B')
"""
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
"""









def factorial_iter(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result








def fibonacci_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


def hanoi(n, source, target, auxiliary):
    if n > 0:
        # 将n-1个盘子从源柱移动到辅助柱
        hanoi(n - 1, source, auxiliary, target)

        # 移动第n个盘子到目标柱
        print(f"移动盘子 {n} 从 {source} 到 {target}")

        # 将n-1个盘子从辅助柱移动到目标柱
        hanoi(n - 1, auxiliary, target, source)


hanoi(3, 'A', 'C', 'B')


def hanoi_visual(n, source='A', target='C', auxiliary='B'):
    towers = {source: list(range(n, 0, -1)), target: [], auxiliary: []}
    print("初始状态:", towers)

    def move_disk(from_tower, to_tower):
        disk = towers[from_tower].pop()
        towers[to_tower].append(disk)
        print(f"移动盘子 {disk} 从 {from_tower} 到 {to_tower}")
        print("当前状态:", towers)

    def hanoi_recursive(n, source, target, auxiliary):
        if n > 0:
            hanoi_recursive(n - 1, source, auxiliary, target)
            move_disk(source, target)
            hanoi_recursive(n - 1, auxiliary, target, source)

    hanoi_recursive(n, source, target, auxiliary)


hanoi_visual(3)

import turtle


def hanoi_turtle(n):
    screen = turtle.Screen()
    screen.setup(800, 600)
    screen.title("汉诺塔可视化")

    t = turtle.Turtle()
    t.speed(0)
    t.hideturtle()

    # 绘制柱子
    for i, pos in enumerate([-200, 0, 200]):
        t.penup()
        t.goto(pos, -100)
        t.pendown()
        t.setheading(90)
        t.forward(200)
        t.write(f"{chr(65 + i)}柱", align="center")

    # 初始化盘子
    disks = []
    for i in range(n):
        d = turtle.Turtle()
        d.shape("square")
        d.shapesize(1, (n - i) * 1.5)
        d.color("blue")
        d.penup()
        d.goto(-200, -90 + i * 20)
        disks.append(d)

    def move_disk_visual(disk_num, from_pos, to_pos):
        disk = disks[disk_num - 1]
        y_pos = len([d for d in disks if d.xcor() == to_pos]) * 20 - 90

        # 抬起
        for _ in range(10):
            disk.sety(disk.ycor() + 5)
            turtle.update()
            turtle.delay(50)

        # 横向移动
        step = (to_pos - from_pos) / 20
        for _ in range(20):
            disk.setx(disk.xcor() + step)
            turtle.update()
            turtle.delay(50)

        # 放下
        for _ in range(10):
            disk.sety(disk.ycor() - 5)
            turtle.update()
            turtle.delay(50)

    def hanoi_recursive(n, source, target, auxiliary):
        if n > 0:
            hanoi_recursive(n - 1, source, auxiliary, target)
            move_disk_visual(n, source, target)
            hanoi_recursive(n - 1, auxiliary, target, source)

    turtle.tracer(0, 0)
    hanoi_recursive(n, -200, 200, 0)
    turtle.done()


hanoi_turtle(4)  # 可视化4个盘子的汉诺塔

import os


def traverse_directory(path, indent=0):
    """递归遍历文件夹结构"""
    # 打印当前文件夹名称
    print(' ' * indent + f"[{os.path.basename(path)}]")

    try:
        # 遍历目录内容
        for item in os.listdir(path):
            item_path = os.path.join(path, item)

            if os.path.isdir(item_path):
                # 递归处理子目录
                traverse_directory(item_path, indent + 4)
            else:
                # 打印文件
                print(' ' * (indent + 4) + item)
    except PermissionError:
        print(' ' * indent + "!权限不足，无法访问")


# 使用示例
traverse_directory('.')  # 遍历当前目录


def traverse_with_stats(path, indent=0):
    """带统计信息的文件夹遍历"""
    total_files = 0
    total_size = 0

    print(' ' * indent + f"+ {os.path.basename(path)}/")

    try:
        items = os.listdir(path)
        for item in items:
            item_path = os.path.join(path, item)

            if os.path.isdir(item_path):
                sub_files, sub_size = traverse_with_stats(item_path, indent + 4)
                total_files += sub_files
                total_size += sub_size
            else:
                file_size = os.path.getsize(item_path)
                print(' ' * (indent + 4) + f"- {item} ({file_size} bytes)")
                total_files += 1
                total_size += file_size

    except PermissionError:
        print(' ' * (indent + 4) + "!权限不足")

    # 打印当前目录统计
    print(' ' * indent + f"  [总计: {total_files}个文件, {total_size / 1024:.1f} KB]")
    return total_files, total_size


# 使用示例
traverse_with_stats('.')

import os
import hashlib


def find_duplicates(start_path):
    """查找重复文件"""
    seen_files = {}
    duplicates = []

    for root, dirs, files in os.walk(start_path):
        for filename in files:
            filepath = os.path.join(root, filename)

            # 计算文件哈希（避免文件名不同但内容相同的情况）
            try:
                with open(filepath, 'rb') as f:
                    file_hash = hashlib.md5(f.read()).hexdigest()

                if file_hash in seen_files:
                    duplicates.append((filepath, seen_files[file_hash]))
                else:
                    seen_files[file_hash] = filepath
            except (IOError, PermissionError):
                continue

    return duplicates


# 使用示例
dups = find_duplicates('.')
for dup in dups:
    print(f"重复文件: {dup[0]} 和 {dup[1]}")